package leetcodecompetition.D362;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-09-10-10:57
 * @Description: 1.0
 */
public class T100030 {

    public int minimumMoves(int[][] grid) {
        List<int[]> list = new ArrayList<>();
        List<int[]> list2 = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] > 1) {
                    for (int k = 0; k < grid[i][j] - 1; k++) {
                        list.add(new int[]{i, j});
                    }
                }
                if (grid[i][j] == 0) {
                    list2.add(new int[]{i, j});
                }
            }
        }
        int res = 0;
        List<List<int[]>> ds = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            int[] start1 = list.get(i);
            int[] end1 = list2.get(i);
            int dif1=getDif(start1,end1);
            res+=dif1;
            int max=Integer.MAX_VALUE,maxIndex=-1;
            for (int j = 0; j < ds.size(); j++) {
                List<int[]> d= ds.get(j);
                int[]start2 = d.get(0);
                int[] end2 = d.get(1);
                int dif2 = d.get(2)[0];
                int m=dif1+dif2-getDif(start1,end2)-getDif(start2,end1);
                if (m>max){
                    max = m;
                    maxIndex=j;
                }
            }
            if (maxIndex!=-1){
                res-=max;
                List<int[]> d= ds.get(maxIndex);
                int[]start2 = d.get(0);
                int[] end2 = d.get(1);
                int dif2 = d.get(2)[0];
                List<int[]> add=new ArrayList<>();
                add.add(start1);
                add.add(end2);
                add.add(new int[]{getDif(start1,end2)});
                ds.add(add);
                List<int[]> add2=new ArrayList<>();
                add.add(start2);
                add.add(end1);
                add.add(new int[]{getDif(start2,end1)});
                ds.add(add2);
                ds.remove(maxIndex);
            }else {
                List<int[]> add=new ArrayList<>();
                add.add(start1);
                add.add(end1);
                add.add(new int[]{getDif(start1,end1)});
                ds.add(add);
            }
        }
        return res;
    }

    public int getDif(int[] start, int[] end) {
        return Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]);
    }
}
